<?php
/*
剑指 Offer 30. 包含min函数的栈

难度：简单

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：
各函数的调用总次数不超过 20000 次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


*/

$obj = new Code_Offer30();
$obj->main();

class Code_Offer30
{
    function main()
    {
        $obj = new MinStack();
        $obj->push(-2);
        $obj->push(0);
        $obj->push(-3);
        echo $obj->min();   // 返回 -3.
        $obj->pop();
        echo $obj->top();        //返回 0.
        echo $obj->min();        //返回 -2.
    }
}

class MinStack
{
    public $stack1;     //主栈

    public $stack2;     //辅助栈。存储stack1中所有【非严格降序】的元素

    /**
     * initialize your data structure here.
     */
    function __construct()
    {
        $this->stack1 = new SplStack();
        $this->stack2 = new SplStack();
    }

    /**
     * @param Integer $x
     * @return NULL
     */
    function push($x)
    {
        // 主栈直接压入
        $this->stack1->push($x);

        if ($this->stack2->isEmpty()) {
            // 对于辅助栈，如果为空直接压入；不为空
            $this->stack2->push($x);
        } else {
            // 辅助栈不为空
            if ($this->stack2->top() >= $x) {
                // 如果辅助栈的栈顶元素 >= x，可以把x压入辅助栈
                $this->stack2->push($x);
            } else {
                // 辅助栈的栈顶元素 < x，不能压入x，为了保持两个栈的元素个数相同，把辅助栈的栈顶再压一份到辅助栈
                $this->stack2->push($this->stack2->top());
            }
        }
    }

    /**
     * @return NULL
     */
    function pop()
    {
        // 主栈辅助栈都是直接pop
        $this->stack1->pop();
        $this->stack2->pop();
    }

    /**
     * @return Integer
     */
    function top()
    {
        return $this->stack1->top();
    }

    /**
     * @return Integer
     */
    function min()
    {
        return $this->stack2->top();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * $obj = MinStack();
 * $obj->push($x);
 * $obj->pop();
 * $ret_3 = $obj->top();
 * $ret_4 = $obj->min();
 */